package pers.qianyu.month_202101.date_20210123;

import org.junit.*;

/**
 * 33. 搜索旋转排序数组
 * https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
 *
 * @author mizzle rain
 * @date 2021-01-23 17:39
 */
public class Search {
    public int search(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) return -1;
        int left = 0, right = len - 1, t = nums[len - 1];
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] < t) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        int pivot = left;
        if (pivot == 0) {
            left = 0;
            right = len - 1;
        } else if (target >= nums[0] && target <= nums[pivot - 1]) {
            left = 0;
            right = pivot - 1;
        } else {
            left = pivot;
            right = len - 1;
        }
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left] == target ? left : -1;
    }

    @Test
    public void test1() {
        int result = new Search()
                .search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0);
        System.out.println("result = " + result);
    }
}
